174. Dungeon Game
Hard

The demons had captured the princess and imprisoned her in the bottom-right corner of a dungeon. The dungeon consists of m x n rooms laid out in a 2D grid. Our valiant knight was initially positioned in the top-left room and must fight his way through dungeon to rescue the princess.

The knight has an initial health point represented by a positive integer. If at any point his health point drops to 0 or below, he dies immediately.

Some of the rooms are guarded by demons (represented by negative integers), so the knight loses health upon entering these rooms; other rooms are either empty (represented as 0) or contain magic orbs that increase the knight's health (represented by positive integers).

To reach the princess as quickly as possible, the knight decides to move only rightward or downward in each step.

Return the knight's minimum initial health so that he can rescue the princess.

Note that any room can contain threats or power-ups, even the first room the knight enters and the bottom-right room where the princess is imprisoned.

 

Example 1:

Input: dungeon = [[-2,-3,3],[-5,-10,1],[10,30,-5]]
Output: 7
Explanation: The initial health of the knight must be at least 7 if he follows the optimal path: RIGHT-> RIGHT -> DOWN -> DOWN.

Example 2:

Input: dungeon = [[0]]
Output: 1

 

Constraints:

  • m == dungeon.length
  • n == dungeon[i].length
  • 1 <= m, n <= 200
  • -1000 <= dungeon[i][j] <= 1000
Accepted
129,141
Submissions
383,125
Seen this question in a real interview before?
Companies
Similar Questions

Average Rating: 4.94 (34 votes)

Premium

Solution


Approach 1: Dynamic Programming

Overview

Like many problems with 2D grid, often the case one can apply either the technique of backtracking or dynamic programming.

Specifically, as it turns out, dynamic programming would work perfectly for this problem.

As a general pattern of dynamic programming, usually we construct a array of one or two dimensions (i.e. dp[i]) where each element holds the optimal solution for the corresponding subproblem.

To calculate one particular element in the dp[i] array, we would refer to the previously calculated elements. And the last element that we figure out in the array would be the desired solution for the original problem.

Intuition

Following the above guideline, here is how we break down the problem into subproblems and apply the dynamic programming algorithm.

We are asked to calculate the minimal health point that the knight needs, in order to recuse the princess. The knight would move from the up-left corner of the grid to reach the down-right corner where the princess is located (e.g. as shown in the following graph).

pic

Though the down-right corner is the final destination of the knight, we could start from the destination and deduce backwards the minimal health point that the knight would need at each step along the way.

So starting from the destination where the princess is locked down, as one can see from the following graph, the knight would need at least 6 health points to survive the damage (5 points) caused by the daemon.

pic

Let us now take one step back. Before reaching the destination, there are two possible positions that the knight might situate, i.e. the one right above the destination so that the knight would take a down step, and the one to the left of the destination so that the knight would take a right step.

Let us look at the cell (denoted as cell U) right above the destination, as shown in the following graph. As we know now, the knight should possess at least 6 health points upon reaching the destination. Since at the cell U we have a magic org which would increase the health of knight by 1 point, the knight would just need to possess 5 health points at the arrival of cell U.

pic

As another alternative to reach the destination, the knight might situate at the cell (denoted as cell L) to the left side of the destination, as shown in the following graph. In this case, similarly the knight would encounter a magic orb which would give him a 30-points boost on health. With this boost of health, it would be more than enough for the knight to survive the final daemon in the destination. As a result, the knight just needs to possess the minimal 1 health point upon entering the cell L.

pic

Now that we have calculated the minimal health points that the knight would need before reaching the destination from two of the possible directions, we can carry on to one more step further from the destination. Let us look at the cell (denoted as cell UL) located at the up-left corner from the destination.

Following the same logic as we have seen in the above steps, we could obtain two values for this cell, which represent the minimal health points that the knight would need for each of the directions that he takes. As one can see from the following graph, at the cell UL, if the knight takes a right step next, he would need at least 5+10=155 + 10 = 15 health points, in order to rescue the princess at the end. If he takes a down step next, he would need at least 1+10=111 + 10 = 11 health points.

pic

With all the 3 examples above, we conclude with the following graph where each cell is marked with two minimal health points respectively for each direction that the knight might take, except the destination cell. As one can see, starting from the up-left corner of the grid, the knight would only need 7 health points to rescue the princess.

pic

Algorithm

Given the above intuition, let us see how we can model it with the general code pattern of dynamic programming algorithm.

First, we define a matrix dp[row][col], where the element dp[row][col] indicates the minimal health points that the knight would need, starting from the corresponding dungeon cell dungeon[row][col], in order to reach the destination.

In the following graph, we show what the dp matrix looks like, for the examples that we listed in the intuition section.

pic

The main idea of the algorithm is clear: we need to calculate the values in the dp matrix. And the last value we calculate for the matrix would be the desired solution for the problem.

In order to calculate the values of dp matrix, we start from the down-right corner of the dungeon, and walk following the orders of from-right-to-left and from-down-to-up. Along with each cell in the dungeon, we calculate the corresponding value of dp[row][col] in the matrix.

The value of dp[row][col] is determined by the following conditions:

  • If possible, by taking the right step from the current dungeon cell, the knight might need right_health health points.

  • If possible, by taking the down step from the current dungeon cell, the knight would might down_health health points.

  • If either of the above two alternatives exists, we then take the minimal value of them as the value for dp[row][col].

  • If none of the above alternatives exists, i.e. we are at the destination cell, there are two sub-cases:

    • If the current cell is of magic orb, then 1 health point would suffice.

    • If the current cell is of daemon, then the knight should possess one health point plus the damage points that would be caused by the daemon.

Complexity

  • Time Complexity: O(MN)\mathcal{O}(M \cdot N) where MNM \cdot N is the size of the dungeon. We iterate through the entire dungeon once and only once.

  • Space Complexity: O(MN)\mathcal{O}(M \cdot N) where MNM \cdot N is the size of the dungeon. In the algorithm, we keep a dp matrix that is of the same size as the dungeon.


Approach 2: Dynamic Programming with Circular Queue

Intuition

In the above dynamic programming algorithm, there is not much we can do to optimize the time complexity, other than reducing the costy condition checks with some tricks on the initial values of the dp matrix.

On the other hand, we could reduce the space complexity of the algorithm from O(MN)\mathcal{O}(M \cdot N) to O(N)\mathcal{O}(N) where NN is the number of columns.

First of all, let us flatten the dp matrix into 1D array, i.e. dp[row][col] = dp[row * N + col].

As one might notice in the above process, in order to calculate each dp[i], we would refer to at most two previously calculated dp values, i.e. dp[i-1] and dp[i-N]. Therefore, once we calculate the value for dp[i], we could discard all the previous values that are beyond the range of N.

The above characteristics of the dp array might remind you the container named CircularQueue which could serve as a sliding window to scan a long list.

pic

Indeed, we could use the CircularQueue to calculate the dp array, as we show in the above graph. At any moment, the size of the CircularQueue would not exceed the predefined capacity, which would be N in our case. As a result, we reduce the overall space complexity of the algorithm to O(N)\mathcal{O}(N).

Algorithm

Complexity

  • Time Complexity: O(MN)\mathcal{O}(M \cdot N) where MNM \cdot N is the size of the dungeon. We iterate through the entire dungeon once and only once.

  • Space Complexity: O(N)\mathcal{O}(N) where NN is the number of columns in the dungeon.

Report Article Issue

Comments: 25
chrisstannnn's avatar
Read More

Very good solutions! I like the figures LOL.

15
Reply
Share
Report
liaison's avatar
Read More

hi @merkle_tree In this case, I would say no. You see, the basic idea of Dynamic Programming is to start from the "bottom case" (pun intended), and then progress towards the final result. In our case, the value at the up-left corner of the grid (location [0,0]) is actually the desired "destination", which is exactly why we cannot start from the point.

12
Show 4 replies
Reply
Share
Report
merkle_tree's avatar
Read More

Amazing article, thank you! I'm missing the advantage of starting in the bottom right corner -- could we also solve this if we started at 0,0 as well?

11
Show 3 replies
Reply
Share
Report
mad_coder's avatar
Read More

Hi @liaison ,
I tried solving this problem with DP using the top down approach i.e. start from initial position in upper left position and then try to reach from that position to either right or down and calculating the minimum life required at each step. Finally, the bottom right position in DP matrix will be my answer but I am getting wrong answer for that. Can you please explain why this approach is not correct in this problem ?

11
Show 1 reply
Reply
Share
Report
aboulmagd's avatar
Read More

Nice explanation, BUT

Why does bottom up DP work when initiated from the bottom right cell, and not from the top left cell?

Any intuition/visuals would really help.
I was only able to solve this problem using the former approach, but why is the DP not symmetrical as with other problems (i.e maximum subarray)?

6
Reply
Share
Report
rishabhgpt3's avatar
Read More

why this problem is tagged as Binary Search /

5
Show 1 reply
Reply
Share
Report
aishwaryagoel17's avatar
Read More

One of the best articles . Thanks !

3
Reply
Share
Report
keertsur's avatar
Read More

Amazing article. I loved it. Thank you :)

1
Reply
Share
Report
jesse1204's avatar
Read More

The best article I've ever seen on Leetcode

1
Reply
Share
Report
piofusco's avatar
Read More

To anyone (else) who's intuition led them to think of Bellman Fords because of the negative weights, it's not a trivial application of the algorithm given the dungeon is an N by M matrix.

Turning this matrix into a graph would require the creation of a root node and then figuring out how to associate the weights in the matrix to each node. This would exhaust the time and space explained in the DP solutions above without even giving the solution.

Staff feedback welcome :)

1
Reply
Share
Report
Success
Details
Runtime: 8 ms, faster than 63.68% of C++ online submissions for Dungeon Game.
Memory Usage: 8.9 MB, less than 40.32% of C++ online submissions for Dungeon Game.
Time Submitted
Status
Runtime
Memory
Language
06/18/2021 12:38Accepted8 ms8.9 MBcpp
03/25/2021 19:30Accepted8 ms9.1 MBcpp
06/21/2020 14:53Accepted12 ms9.2 MBcpp
/23
Contribute
|||
Saved
Trie
This list is empty.